package subject_set.offer100;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author haomin
 * @date 2022/10/13 19:55
 **/
public class Offer03 {
    class Solution {
        // 方法一：Set集合
        public int findRepeatNumber1(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int i : nums) {
                if(!set.add(i)) return i;
            }
            return -1;
        }

        // 方法二：排序
        public int findRepeatNumber2(int[] nums) {
            Arrays.sort(nums);
            for(int i = 1; i < nums.length; ++i) {
                if(nums[i] == nums[i-1]) return nums[i];
            }
            return -1;
        }

        // 方法三： 元素归位
        public int findRepeatNumber(int[] nums) {
            int i = 0;
            while(true) {
                int m = nums[i];
                int n = nums[m];
                if(m == i) i++;
                else if(m == n) return m;
                else {
                    nums[m] = m;
                    nums[i] = n;
                }
            }
        }
    }
}